package com.linyaonan.leetcode.sword_to_offer._66;


import java.math.BigInteger;
import java.util.ArrayList;

/**
 * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 *
 *  
 *
 * 示例:
 *
 * 输入: [1,2,3,4,5]
 * 输出: [120,60,40,30,24]
 *  
 *
 * 提示：
 *
 * 所有元素乘积之和不会溢出 32 位整数
 * a.length <= 100000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public int[] constructArr(int[] a) {

        if (a == null || a.length == 0) {
            return a;
        }

        int all = 1;
        ArrayList<Integer> zeroList = new ArrayList<>();
        boolean hasZero = false;

        for (int i = 0; i < a.length; i++) {
            int num = a[i];
            if (num != 0) {
                all *= num;
            } else {
                hasZero = true;
                zeroList.add(i);
            }
        }


        int[] r = new int[a.length];
        if (zeroList.size() >= 2) {
            return r;
        }

        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) {
                r[i] = all;
            } else {
                if (hasZero) {
                    r[i] = 0;
                } else {
                    r[i] = division2(all, a[i]);
                }
            }
        }

        return r;
    }

    private int division(int a, int b) {
        boolean tong = false;
        if ((a > 0 && b > 0) || (a < 0 && b < 0)) {
            tong = true;
        }
        a = Math.abs(a);
        b = Math.abs(b);
        int count = 0;
        while (a != 0) {
            a -= b;
            count++;
        }
        if (tong) {
            return count;
        } else {
            return 0 - count;
        }
    }

    private int division2(int a, int b) {
        BigInteger aI = BigInteger.valueOf(a);
        BigInteger bI = BigInteger.valueOf(b);
        return aI.divide(bI).intValue();
    }
}